package com.yuufa.test.recursive;

import java.math.BigInteger;

import com.yuufa.util.Tool;

public class Main {

    public static void main(String[] args) {
    
    }
}

class Comb {

    public static void test() {
        int n = 50;
        int m = 27;

        System.out.println(_combUse1Array(n, m));
        System.out.println(_combUse2Array(n, m));
        // System.out.println(comb(n, m));
        // System.out.println(_comb(n, m));
    }

    public static BigInteger _combUse1Array(int n, int m) {
        
        BigInteger[] s = new BigInteger[n + 1];

        for (int i = 1; i <= n; i++) {
            s[i] = new BigInteger(""+i, 10);
        }

        for (int k = 2; k <= m; k++) {
            for (int j = 2; j <= n; j++) {
                s[j] = s[j].add(s[j - 1]);
            }
        }

        return s[n - m + 1]; // 
    }

    public static int _combUse2Array(int n, int m) {

        int[][] s = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            s[i][i] = 1;
            s[i][1] = i;
        }

        for (int j = 2; j <= m; j++) {
            for (int i = j + 1; i <= n; i++) {
                s[i][j] = s[i - 1][j] + s[i - 1][j - 1];
            }
        }

        return s[n][m];
    }

    public static int _comb(int n, int m) {

        int result = 0;
        int[][] s = new int[n + 1][2];
        int sp = -1;

        ++sp;
        s[sp][0] = n;
        s[sp][1] = m;

        while (sp != -1) {
            n = s[sp][0];
            m = s[sp][1];
            sp--;

            if (n == m || m == 0) {
                result = result + 1;
            } else {
                ++sp;
                s[sp][0] = n - 1;
                s[sp][1] = m - 1;
                ++sp;
                s[sp][0] = n - 1;
                s[sp][1] = m;
            }
        }

        return result;
    }

    public static int comb(int n, int m) {

        if (m == 0 || n == m) {
            return 1;
        } else {
            return comb(n - 1, m - 1) + comb(n - 1, m);
        }
    }
}

class Maze {

    public static void test() {
        maze(1, 1);
    }

    static int[][] m = {{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 1, 1}, {1, 1, 1, 0, 1, 0, 1, 0, 1, 1}, {1, 1, 1, 0, 1, 1, 1, 0, 0, 1}, {1, 1, 1, 0, 0, 0, 1, 1, 0, 1}, {1, 1, 1, 1, 1, 0, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};

    static int[][] visited = {{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};

    static int[][] forward = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    static int d = 4;

    static int sp = -1;
    static int[][] xy = new int[1000][2];

    public static void maze(int i, int j) {

        visited[i][j] = 1;
        sp++;
        xy[sp][0] = i;
        xy[sp][1] = j;

        if (i == 6 && j == 8) {
            for (int x = 0; x < 8; x++) {
                for (int y = 0; y < 10; y++) {
                    System.out.printf("%2d", visited[x][y]);
                }
                System.out.println();
            }

            System.out.println();

            for (int k = 0; k <= sp; k++) {
                System.out.print(String.format("(%d,%d)->", xy[k][0], xy[k][1]));
            }
        } else {
            for (int r = 0; r < d; r++) {
                int ti = i + forward[r][0];
                int tj = j + forward[r][1];

                if (m[ti][tj] == 0 && visited[ti][tj] == 0) {
                    maze(ti, tj);
                }
            }
            visited[i][j] = 0;
            sp--;
        }
    }
}

class NQueen {

    static int n = 4;
    static int[] s = new int[n + 1];

    public static void test() {
        queen(1);
    }

    public static boolean promising(int i) {

        int row = 1;
        boolean result = true;

        while (row < i) {
            if (s[row] == s[i] || (i - row) == Math.abs(s[row] - s[i])) {
                result = false;
            }
            row++;
        }

        return result;
    }

    public static void queen(int i) {

        if (i > n) {
            Tool.print(s, 1, n);
        } else {
            for (int j = 1; j <= n; j++) {
                s[i] = j;
                if (promising(i)) {
                    queen(i + 1);
                }
            }
        }
    }
}

class Hanoi {

    static int m = 3;

    public static void test1() {

        hanoi('a', 'b', 'c', m);
    }

    public static void test2() {

        hanoiUseStack('a', 'b', 'c', m);
    }

    public static void hanoiUseStack(char a, char b, char c, int n) {

        int[][] s = new int[1000][4];
        int sp = -1;

        sp++;
        s[sp][0] = a;
        s[sp][1] = b;
        s[sp][2] = c;
        s[sp][3] = n;

        while (sp != -1) {
            a = (char) s[sp][0];
            b = (char) s[sp][1];
            c = (char) s[sp][2];
            n = s[sp][3];
            sp--;

            if (n == 1) {
                System.out.print(a + "->" + c + ",");
            } else {
                sp++;
                s[sp][0] = b;
                s[sp][1] = a;
                s[sp][2] = c;
                s[sp][3] = n - 1;
                sp++;
                s[sp][0] = a;
                s[sp][1] = b;
                s[sp][2] = c;
                s[sp][3] = 1;
                sp++;
                s[sp][0] = a;
                s[sp][1] = c;
                s[sp][2] = b;
                s[sp][3] = n - 1;
            }

        }

    }

    public static void hanoi(char a, char b, char c, int n) {

        if (n == 1) {
            System.out.print(a + "->" + c + ",");
        } else {
            hanoi(a, c, b, n - 1);
            System.out.print(a + "->" + c + ",");
            hanoi(b, a, c, n - 1);
        }
    }
}

class Subset {

    static char[] s = {'a', 'b', 'c', 'd'};
    static int n = s.length;

    public static void test() {

        char[] atom = new char[n];

        subset(atom, 0, 0, n);
    }

    public static void subset(char[] atom, int m, int i, int n) {

        if (i == n) {
            for (int k = 0; k < m; k++) {
                System.out.print(atom[k]);
            }
            System.out.println();
        } else {
            subset(atom, m, i + 1, n);
            atom[m] = s[i];
            subset(atom, m + 1, i + 1, n);
        }
    }
}

class ReverStr {

    static String str = "15510";

    public static void test() {
        reverse(0);
    }

    public static void reverse(int index) {
        if (index != str.length()) {
            reverse(index + 1);
            System.out.print(str.charAt(index));
        }
    }
}

class Permutation {

    public static void test() {

        char[] s = {'a', 'b', 'c'};
        int n = s.length;

        permutation(s, 0, n - 1, n);
    }

    public static void permutation(char[] s, int first, int last, int n) {

        if (first == last) {
            for (int i = 0; i < n; i++) {
                System.out.print(s[i]);
            }
            System.out.println();
        } else {
            for (int i = first; i <= last; i++) {
                char t = s[first];
                s[first] = s[i];
                s[i] = t;
                permutation(s, first + 1, last, n);
                t = s[first];
                s[first] = s[i];
                s[i] = t;
            }
        }
    }
}

class Fib {

    public static void test() {
        int n = 7;

        fib(n);
        fn(n);
        int value = f(n);

        System.out.println(value);
    }

    public static void fib(int n) {

        if (n == 0 || n == 1) {
            System.out.println(n);
        } else {
            int[] s = new int[n + 1];
            s[0] = 0;
            s[1] = 1;

            for (int i = 2; i <= n; i++) {
                s[i] = s[i - 1] + s[i - 2];
            }

            System.out.println(s[n]);
        }
    }

    public static void fn(int n) {

        int f0 = 0;
        int f1 = 1;
        int fn = -1;

        if (n == 0) {
            System.out.println(f0);
        } else if (n == 1) {
            System.out.println(f1);
        } else if (n > 1) {
            for (int i = 2; i <= n; i++) {
                fn = f0 + f1;
                f0 = f1;
                f1 = fn;
            }
            System.out.println(fn);
        }
    }

    public static int f(int n) {
        if (n == 1 || n == 0) {
            return n;
        } else {
            return f(n - 1) + f(n - 2);
        }
    }
}
